

export class WeightedGraph {
    private matrix: number[][];
    private numVertices: number;
    private nodeStates: boolean[]; // 记录每个节点的开启/关闭状态
  
    constructor(numVertices: number) {
      this.numVertices = numVertices;
      this.matrix = new Array(numVertices);
      this.nodeStates = new Array(numVertices).fill(true); // 默认所有节点为开启状态
  
      // 初始化邻接矩阵
      for (let i = 0; i < numVertices; i++) {
        this.matrix[i] = new Array(numVertices).fill(Infinity);
        this.matrix[i][i] = 0; // 节点到自身的距离为0
      }
    }
  
    /**
     * 添加带权重的边（无向图）
     * @param v 起点
     * @param w 终点
     * @param weight 权重值（需为正数）
     */
    addEdge(v: number, w: number, weight: number): void {
      if (weight < 0) throw new Error("Dijkstra不支持负权重");
      this.matrix[v][w] = weight;
      this.matrix[w][v] = weight; // 无向图需要双向设置
    }
  
    /**
     * 设置节点的开启/关闭状态
     * @param node 节点索引
     * @param state 状态（true为开启，false为关闭）
     */
    setNodeState(node: number, state: boolean): void {
      if (node < 0 || node >= this.numVertices) throw new Error("节点索引无效");
      this.nodeStates[node] = state;
    }

    /**
     * 获取节点的开启/关闭状态
     * @param node 节点索引
     * @returns 状态（true为开启，false为关闭）
     */
    getNodeState(node: number): boolean {
      if (node < 0 || node >= this.numVertices) throw new Error("节点索引无效");
      return this.nodeStates[node];
    }
  
    /**
     * Dijkstra算法实现（考虑节点状态）
     * @param start 起始节点
     * @returns 起始节点到所有节点的最短距离数组
     */
    private dijkstra(start: number): number[] {
      const dist: number[] = new Array(this.numVertices).fill(Infinity);
      const visited: boolean[] = new Array(this.numVertices).fill(false);
  
      dist[start] = 0; // 起点到自身距离为0
  
      for (let i = 0; i < this.numVertices - 1; i++) {
        // 找到当前未访问节点中距离最小的
        const u = this.minDistance(dist, visited);
        if (u === -1) break; // 如果没有可达节点，提前退出
        visited[u] = true;
  
        // 更新所有相邻节点的距离
        for (let v = 0; v < this.numVertices; v++) {
          if (
            !visited[v] &&
            this.nodeStates[v] && // 目标节点必须为开启状态
            this.matrix[u][v] !== Infinity &&
            dist[u] + this.matrix[u][v] < dist[v]
          ) {
            dist[v] = dist[u] + this.matrix[u][v];
          }
        }
      }
      return dist;
    }
  
    /**
     * 计算两点间的最短距离（考虑节点状态）
     * @param start 起始节点
     * @param end 目标节点
     * @returns 最短距离（若不可达返回 Infinity）
     */
    shortestPath(start: number, end: number): number {
      if (start === end) return 0;
      if (!this.nodeStates[start] || !this.nodeStates[end]) return Infinity; // 起点或终点关闭
      const distances = this.dijkstra(start);
      return distances[end];
    }
  
    /** 辅助方法：找到未访问节点中的最小距离节点 */
    private minDistance(dist: number[], visited: boolean[]): number {
      let min = Infinity;
      let minIndex = -1;
  
      for (let v = 0; v < this.numVertices; v++) {
        if (!visited[v] && this.nodeStates[v] && dist[v] <= min) {
          min = dist[v];
          minIndex = v;
        }
      }
      return minIndex;
    }
  
    /** 打印邻接矩阵 */
    printMatrix(): void {
      console.log("Adjacency Matrix:");
      console.log("   " + [...Array(this.numVertices).keys()].join("  "));
      this.matrix.forEach((row, i) => {
        console.log(
          `${i} [${row.map(x => x === Infinity ? "∞" : x).join(", ")}]`
        );
      });
    }
  
    /** 打印节点状态 */
    printNodeStates(): void {
      console.log("Node States:");
      this.nodeStates.forEach((state, i) => {
        console.log(`Node ${i}: ${state ? "Open" : "Closed"}`);
      });
    }
}